In many electronic systems there are situations where several modules wish to use a common resource simultaneously. Examples include microprocessor systems where a decision is required concerning which of several interrupts to service first, multiprocessor environments where several processors wish to use some device concurrently, and data communication networks with shared media. To resolve conflicts, an arbitration mechanism is required that grants the resource to one module at a time.
Numerous arbitration mechanisms have been developed, including daisy chains, priority circuits, polling, token passing, and carrier sense protocols, to name a few. A distinction is made between centralized arbiters, where a specific module is responsible for arbitrating, and distributed arbiters, where the arbitration process is carried out simultaneously at all the system modules. In many modern systems, and especially in multiprocessor environments and data communication networks, distributed arbitration is the preferred mechanism due to its reliability, easy expansion and simple monitoring.
Typically, a distributed arbitration mechanism employs a collection of arbitration busses to implement priority arbitration. To this end, each module is assigned a unique arbitration priority, which is an encoding of its name or address. During arbitration between contending modules, each contending module asserts its arbitration priority onto the arbitration busses according to an arbitration protocol. The arbitration protocol determines logic values that a contending module applies to the arbitration busses, based on the contending module's arbitration priority and on logic values on the busses. After completion of an arbitration process, the settled logic values on the arbitration busses uniquely identify the contending module with the highest priority.
An example of a distributed priority arbitration mechanism is the asynchronous binary arbitration scheme (also called "encoded arbitration") developed by D. M. Taub in "Contention-Resolving Circuits for Computer Interrupt Systems", Proceedings of the IEE, Volume 123, No. 9, September 1976, Pages 845-850. The asynchronous binary arbitration scheme has gained popularity and is used in many modern bus systems such as Futurebus, M3-bus, S-100 bus, Multibus-II, Fastbus, and Nubus. This asynchronous arbitration scheme arbitrates among n modules in at most t= lg n units of time, using m= lg n open-collector (wired-OR) arbitration busses. (Hereinafter only arbitration busses that are used for encoding the arbitration priorities are counted. Several additional control busses are understood to be used by all schemes and are not counted.)
Each module is assigned a unique ( lg n )-bit arbitration priority. When arbitration begins, competing modules apply their arbitration priorities to the m= lg n busses, each bit on a separate bus. The busses are initially at logic level 0. The open-collector busses implement a bitwise OR of the asserted arbitration priorities. That is, the open-collector busses provide a default logic value of 0 on a bus, unless at least one module applies a logic value of 1 to the bus, in which case the logic value on the bus becomes a 1. The open-collector busses, thus, OR together the logic values applied to them, with some time delay referred to as "bus-settling delay".
During arbitration, each competing module monitors the arbitration busses and disables its drivers according to the following rule: if the module is applying a 0 (that is, not applying a 1) to a particular bus but detects that the bus is carrying a 1 (applied by some other competing module), it ceases to apply all its bits of lower significance than that of the bit (0) applied to the particular bus. Disabled bits are re-enabled when the condition ceases to hold. This rule is continuously applied to all the bus drivers. The effect of this rule is that the arbitration process proceeds in at most lg n stages, each taking one unit of bus-settling delay, from the most significant bit to the least significant bit of the arbitration priorities.
In the worst case, each unit of time delay (stage) consists of resolving the binary value of another bit of the competing module with the highest priority, from the most significant bit down to the least significant bit. This leads to a worst case arbitration time of t= lg n (in units of bus-settling delay).
Another commonly used priority arbitration mechanism is the linear arbitration scheme. This scheme uses m=n busses and arbitrates among n modules in t=1 stage. Each module is assigned an n-bit arbitration priority which includes only one bit having binary value 1. The 1-bit of different modules is asserted onto different busses. Thus, during arbitration, contending module c.sub.i applies a 1 to arbitration bus b.sub.i for 0.ltoreq.i.ltoreq.n-1 and does not interfere with other busses. Initially, the busses are all at logic level 0. After t=1 unit of time (bus-settling delay), all the arbitration busses stabilize to their final values and the module with a 1 on the arbitration bus with the highest priority is recognized as the winner. This scheme can also be implemented with tri-state busses, since at most one module writes to any given bus. The scheme is also known as "decoded arbitration" and is used in a number of bus systems and interrupt arbitration mechanisms.
The focus of the present invention is on asynchronous priority arbitration systems that employ m arbitration busses for lg n .ltoreq.m.ltoreq.n. In these systems, the arbitration circuitry on the modules together with the arbitration busses form a purely combinational acyclic circuit. That is, there are no storage elements or feedback paths in the arbitration logic. Further, the only means of communication between modules is through the system-wide busses.
An arbitration process, once started, runs asynchronously until its completion. That is, the arbitration process does not use any clock signals during its progress. An important parameter in such systems is the maximal delay required to complete any arbitration process in the system. This parameter is referred to as "arbitration time". A common practice is to measure the arbitration time in units of bus-settling delay, which is the time it takes a bus to reach a stable logic value once its drivers have stabilized. This unit of time is meant to include the delays introduced by the logic gates, drivers, bus-propagation delay, and any additional time required to resolve transient effects on the bus. An open-collector (wired-OR) bus is modelled as an OR gate with delay of bus-settling time. Arbitration processes are analyzed as a sequence of stages, each of duration of one bus-settling delay.
Reducing the arbitration time is of primary importance in system design. Whether the system employs global or local clocks and allocates a certain amount of time for arbitration, or the system employs self-timed logic, minimizing the duration of arbitration processes is a fundamental concern. For example, D. Del Corso and L. Verrua in "Contention Delay in Distributed Priority Networks", Microprocessing and Microprogramming, volume 13, no. 1, January 1984, pages 21-29, develop a technique to reduce the arbitration time of the asynchronous binary arbitration scheme of Taub by one unit of bus-settling delay. Their technique involves using m= lg(n+1) arbitration busses, and eliminating one m-bit codeword to reduce the arbitration time of binary arbitration to t= lg(n+1) -1.
The foregoing commonly used asynchronous priority arbitration schemes present the extremes in the trade-off between the number of arbitration busses required and the arbitration time. The bus-time trade-off is of great practical interest to system designers who desire a certain balance between the amount of hardware and speed. Accordingly, there is a need for an asynchronous priority arbitration system with a balance between the number of arbitration busses employed and the arbitration time.